This invention relates to a system for locating a vehicle and guiding it along its route, in which the vehicle's position in an area represented by a digitized map database is continuously determined. Since navigation and route guidance decisions are based on this continuously-determined position, it is necessary that the position be determined accurately.
In known vehicle navigation systems, a vehicle's position is continuously determined in relative or absolute X-Y coordinates. This position determination is absolute, if determined, for example, by GPS (Global Positioning System) or Loran C, or relative, if determined by dead reckoning through the continuous integration of successive displacement vectors. However, the position so determined in either case is not always accurate. Because of errors in sensing and computation, the positions reported by the system may depart from actual vehicle positions. Thus a travel route as reported by the system may fail to match the roads delineated in the database.
Past attempts to match the travel route to a map make use of conventional pattern-matching to compare the vehicle's route with known roads close to the previous matched position. The road whose shape most closely approaches the previously matched road is selected as the one on which the vehicle must be traveling. Such a process takes considerable time if there are many roads and branches of roads in the area.
U.S. Pat. No. 4,963,864 discloses another method, where pattern matching is performed for only a limited number of roads, thereby reducing the time required. A road is selected if the angle between the vector of current motion, as determined by GPS, Loran C, or dead reckoning, is within a predetermined value of the vector extending from the assumed current position. Pattern-matching between the road pattern selected and the vehicle's trajectory gives the position on the map, and the process is speeded up because only a limited number of roads is considered for matching. The computational load, although reduced, is still considerable, and the reduction in the number of roads considered may exclude the road on which the vehicle is actually located. Thus, the above methods fail to overcomes fully the drawbacks of incorrect positioning.